package com.company.project.learning.zaluan;

/**
 * @Author: zhaoqi
 * @Date: 11/13/2019 11:23 AM
 * @Version 1.0
 */

public class Sort3 {

    public static void main(String[] args) {
        int[] array = {6,98,5,54,2};

       // Sort3.sort(array,);
    }

    public static void sort(int[] a, int low, int high) {
        //已经排完
        if (low >= high) {
            return;
        }
        int left = low;
        int right = high;

        //保存基准值
        int pivot = a[left];
        while (left < right) {
            //从后向前找到比基准小的元素
            while (left < right && a[right] >= pivot)
                right--;
            a[left] = a[right];
            //从前往后找到比基准大的元素
            while (left < right && a[left] <= pivot)
                left++;
            a[right] = a[left];
        }
        // 放置基准值，准备分治递归快排
        a[left] = pivot;
        sort(a, low, left - 1);
        sort(a, left + 1, high);
    }

    public Sort3() {
    }
}
